package binaryTree;

public class BinaryTree {
    private int nodeSize;
    static class TreeNode{
        //树的节点-孩子表示法
        public char val;
        private TreeNode left;
        private TreeNode right;
        public TreeNode(char val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }

    public TreeNode createTree() {
        //通过穷举的方式创建一棵树，并返回根节点
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = H;
        C.left = F;
        C.right = G;
        return A;
    }

    //前序遍历方式 根-》左-》右
    public void preorderTraversal(TreeNode base) {
        /**
         * 无需操心具体是如何递归实现的，只需知道这种方式即可*/
        if(base==null) {
            return;
        }
        System.out.print(base.val+" ");
        preorderTraversal(base.left);
        preorderTraversal(base.right);
    }

    //中序遍历方式 左-》根-》右
    public void inorderTraversal(TreeNode base) {
        if(base==null) {
            return;
        }
        inorderTraversal(base.left);
        System.out.print(base.val+" ");
        inorderTraversal(base.right);
    }

    //后序遍历方式 左-》右-》根
    public void postorderTraversal(TreeNode base) {
        if(base==null) {
            return;
        }
        postorderTraversal(base.left);
        postorderTraversal(base.right);
        System.out.print(base.val+" ");
    }

    //获取树中的节点个数
    public int size(TreeNode base) {
        //通过大问题化小问题的思路-》总节点数==左树节点数+右数节点数+自己
        if(base==null) {
            return 0;
        }
        return size(base.left)+size(base.right)+1;
    }

    //获取数中叶子节点的个数
    public int leafNode(TreeNode base) {
        if(base==null) {
            return 0;
        }
        if(base.right==null && base.left==null) {
            return 1;
        }
        return leafNode(base.left)+leafNode(base.right);
    }

    // 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode base,int k) {
//        if(k==1 && base!=null) {
//            return 1;
//        }
//        if(k==1 && base==null) {
//            return 0;
//        }
//        if(base==null) {
//            return 0;
//        }
        if(base==null) {
            return 0;
        }
        if(k==1) {
            return 1;
        }
        return getKLevelNodeCount(base.left,k-1) + getKLevelNodeCount(base.right,k-1);
    }

    // 获取二叉树的高度
    public int getHeight(TreeNode base) {
        //当递归到null时，此时高度需要减一
        if(base==null) {
            return 0;
        }
        //整棵树的高度==左子树的高度+右子树的高度+自己的高度
        return Math.max(getHeight(base.left),getHeight((base.right))) + 1;
    }

    // 检测值为value的元素是否存在
    /**
     * 先判断当前节点是否为null，若为null则直接返回null
     * 再判断当前节点val值是否为指定val值，若是，直接返回该节点
     * */
    public TreeNode find(TreeNode base, int val) {
        if(base == null) {
            return null;
        }
        if(base.val == val) {
            return base;
        }
        TreeNode ret1 = find(base.left,val);
        if(ret1!=null) {
            return ret1;
        }
        TreeNode ret2 = find(base.right,val);
        if(ret2!=null) {
            return ret2;
        }
        return null;
    }
    //层序遍历
//    void levelOrder(Node root);
//    // 判断一棵树是不是完全二叉树
//    boolean isCompleteTree(Node root);

}
